import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Solution {
    public int alternateDigitSum(int n) {
        int ans = 0, flg = -1;
        while(n > 0){
            ans += flg*n%10;
            flg = -flg;
            n /= 10;
        }
        return -flg*ans;
    }
}

/*class Solution {
    public long max = Long.MIN_VALUE;
    public long path = 0;
    public void dfs(int[] nums, int i, int k){
        if(path > max){
            max = path;
        }
        for(int j=i; j<nums.length; j++){
            if(k%2 == 1){
                path -= nums[j];
            }else{
                path += nums[j];
            }
            dfs(nums,j+1,k+1);
            if(k%2 == 1){
                path += nums[j];
            }else{
                path -= nums[j];
            }
        }
    }
    public long maxAlternatingSum(int[] nums) {
        dfs(nums,0,1);
        return max;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] num = {4,2,5,3};
        s.maxAlternatingSum(num);
    }
}*/
public class Test {
    public static void main(String[] args) {
        List<List<TreeNode>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<TreeNode> ans = new ArrayList<>();
            for (int i = 0; i < queue.size(); i++) {
                ans.add(queue.poll());
                TreeNode cur = ans.get(i);
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(ans);
        }
    }
}
//106
class Solution {//左右根
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int pEnd = postorder.length - 1;
        this.last = postorder.length - 1;
        return createTree(inorder,postorder,0,pEnd);
    }
    private int last = 0;
    public TreeNode createTree(int[] inorder, int[] postorder, int inBeign, int inEnd){
        if(inBeign > inEnd){
            return null;
        }
        if(last < 0) return null;
        int mid = find(inorder, inBeign, inEnd, postorder[last]);
        TreeNode root = new TreeNode(postorder[last]);
        last--;
        root.right = createTree(inorder, postorder, mid+1, inEnd);
        root.left = createTree(inorder, postorder, inBeign, mid-1);
        return root;
    }
    public int find(int[] inorder, int ib, int ie, int target){
        for(int i=ib; i<=ie; i++){
            if(inorder[i] == target){
                return i;
            }
        }
        return -1;
    }
}
//105
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int inEnd = inorder.length - 1;
        return createTree(preorder,inorder,0, inEnd);
    }
    private int first = 0;
    public TreeNode createTree(int[] preorder, int[] inorder, int inBegin,int inEnd){
        if(inBegin > inEnd){
            return null;
        }
        int mid = find(inorder, inBegin, inEnd, preorder[first]);
        TreeNode root = new TreeNode(preorder[first]);
        first++;
        root.left = createTree(preorder,inorder,inBegin,mid-1);
        root.right = createTree(preorder,inorder,mid+1,inEnd);
        return root;
    }

    public int find(int[] inorder, int ib, int ie, int target){
        for(int i=ib; i<=ie; i++){
            if(inorder[i] == target){
                return i;
            }
        }
        return -1;
    }
}
//102 - 队列实现
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList();
        if(root == null) return ans;
        Queue<TreeNode> cur = new LinkedList();
        cur.offer(root);
        while(!cur.isEmpty()){
            List<Integer> ret = new LinkedList();
            int n = cur.size();
            for(int i=0; i<n; i++){
                TreeNode tmp = cur.poll();
                ret.add(tmp.val);
                if(tmp.left != null) cur.offer(tmp.left);
                if(tmp.right != null) cur.offer(tmp.right);
            }
            ans.add(ret);
        }
        return ans;
    }
}
